package Algorithm.SortAlgorithm;

/**
 * 快速排序类
 */
public class QuickSort {

    int[] arr;

    /**
     * 快速排序的主方法
     *
     * @param arr 待排序的数组
     */
    public void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        this.arr = arr;
        quickSortRecursive(0, arr.length - 1);
        for (int i = 0; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
    }

    /**
     * 快速排序的递归方法
     *
     * @param left  当前分区的最左索引
     * @param right 当前分区的最右索引
     */
    private void quickSortRecursive(int left, int right) {
        if (left >= right) {
            return;
        }

        int pivotIndex = partition(left, right);

        // 对左右两边递归
        quickSortRecursive(left, pivotIndex - 1);
        quickSortRecursive(pivotIndex + 1, right);
    }

    /**
     * 分区函数：以最后一个元素为基准
     */
    private int partition(int left, int right) {
        int pivot = arr[right];
        int i = left;

        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                swap(i, j);
                i++;
            }
        }

        swap(i, right); // 把基准元素放到正确位置
        return i;
    }

    /**
     * 交换数组中的两个元素
     */
    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{1,3,2,1,5,7,6,4};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr);
    }
}
